PrecSezione 5.4: Gestione degli errori di trasmissione SuCapitolo 5: Trasmissione dati in banda base Sezione: AppendiciSegue

## 5.5Protocolli ARQ

Le trasmissioni arq prevedono l’esistenza di un canale di ritorno, mediante il quale chiedere la ri-trasmissione delle trame ricevute con errori [140] [140]Queste tecniche hanno origine a scopo di controllo degli errori nei collegamenti punto-punto per i quali si osserva una probabilità di errore non trascurabile. Successivamente, sono stati utilizzati nelle reti a pacchetto, in cui è possibile la perdita totale dei pacchetti in transito. Per questo le implementazioni attuali dei arq, specie se applicati da un estremo all’altro di una rete, privilegiano l’uso di timeout piuttosto che quello di riscontri negativi.; pertanto i dati anche se già trasmessi, devono essere temporaneamente memorizzati al trasmettitore, per rispondere alle eventuali richieste del ricevitore. Viene illustrato per primo un metodo molto semplice, ma potenzialmente inefficiente. Adottando invece buffer (detti finestre) di ricezione e trasmissione di dimensioni opportune, si riesce a conseguire una efficenza maggiore.

### 5.5.1Send and wait↓

Viene trasmessa una trama alla volta, e si attende un riscontro (ACKnoledgment↓) di corretta ricezione prima di trasmettere la seguente. Nel caso in cui il ricevitore rilevi un errore, si genera invece un riscontro negativo (NACK↓), che causa la ritrasmissione della trama trasmessa in precedenza. Se il nack giunge illeggibile, il trasmettitore attende fino allo scadere di un allarme a tempo (timeout) e quindi ritrasmette comunque l’ultimo dato inviato.
In figura 5.32↓ è riportata una tipica sequenza di passaggi, in cui (a) la trama N+ 2 è ricevuta con errore, causando un primo nack; quindi (b) è l’ack(N+ 3) ad arrivare errato, causando lo scadere del timeout, e la ritrasmissione della trama N+ 3. Notiamo che le trame devono essere etichettate con un numero di sequenza, in modo da permettere al ricevitore, nel caso (b), di riconoscerela trama come duplicata, e scartarla (l’ack è inviato comunque per permettere la risincronizzazione del trasmettitore).
Figura 5.32  Richieste di ritrasmissione per un protocollo send and wait
Utilizzo del collegamento↓
Considerando l’intervallo di tempo tT che intercorre tra la trasmissione di due trame consecutive, la trasmissione vera e propria dura solamente tTx istanti, dopodiché occorre attendere 2⋅tp istanti (tp è il tempo di propagazione) prima di ricevere l’ack. Trascurando gli altri tempi (di trasmissione dell’ack, e di elaborazione delle trame), si definisce una efficienza di utilizzo
U=(tTx)/(tT)≃(tTx)/(tTx+ 2⋅tp)=(1)/(1 + 2⋅tp⁄tTx)=(1)/(1 + 2⋅a)
in cui il parametro a che determina il risultato, può assumere valori molto diversi, in funzione della velocità di trasmissione e della lunghezza del collegamento.
Esempio Una serie di trame di N= 1000 bit viene trasmessa utilizzando un protocollo send-and-wait, su tre diversi collegamenti:

- a) un cavo ritorto di 1 km,
  b) una linea dedicata di 200 km,
  c) un collegamento satellitare di 50000 km.
  Sapendo che la velocità di propagazione è di 2⋅108 m/sec per i casi (a) e (b), e di 3⋅108 m/sec per il caso (c), determinare l’efficienza di utilizzo U=(1)/(1 + 2⋅a), per le due possibili velocità di trasmissione fb di 1 kbps ed 1 Mbps. □
  Il tempo necessario alla trasmissione tTx=(N)/(fb), risulta pari ad 1 sec ed 1 msec alle velocità di 103 e 106 bps rispettivamente. Il tempo di propagazione tp=(spazio)/(velocità) risulta pari a 5⋅10− 6 sec, 1⋅10− 3 sec e 0.167 sec nei tre casi (a), (b), e (c) rispettivamente. Pertanto:
  a) si ottiene a=(tp)/(tTX)= 5⋅10− 6 e a= 5⋅10− 3 per le velocità di 1 kbps ed 1 Mbps rispettivamente, e quindi per entrambe U≃1;
  b) per fb= 1 kbps si ottiene a=  10− 3 e quindi U≃1, per fb= 1 Mbps risulta a= 1 e quindi U= 0.33;
  c) per le velocità di 1 kbps ed 1 Mbps si ottiene a= 0.167 ed a= 167 rispettivamente, a cui corrispondono efficienze pari a U= 0.75 e U= 0.003.

Sulla base del risultato dell’esempio notiamo che, considerando fissa la dimensione di trama, le prestazioni di un collegamento nei confronti di un protocollo arq possono essere caratterizzate, oltre che dal parametro a, anche dal cosiddetto Prodotto Banda-Ritardo PBR=fb⋅tp, che infatti nei sei casi in esame vale 5⋅10− 3,   5,  1,  103,  160,  1.6⋅105. Pertanto, abbiamo dimostrato come la trasmissione send and wait possa essere idonea per basse velocità e/o collegamenti brevi, in virtù della sua semplicità realizzativa; in caso contrario, è opportuno ricorrere ad uno dei metodi seguenti.

### 5.5.2Continuous RQ

A differenza del protocollo send-and-wait, ora il trasmettitore invia le trame ininterrottamente, senza attendere la ricezione degli ack. In presenza di trame ricevute correttamente, il ricevitore riscontra positivamente le stesse, consentendo al trasmettitore di liberare i buffer di trasmissione. In presenza di trame ricevute con errori, la quantità di memoria tampone utilizzata al ricevitore determina la scelta di due possibili strategie di richiesta di ritrasmissione, denominate go-back-N e selective-repeat.

#### 5.5.2.1Go back N

In questo caso, il ricevitore dispone di una sola posizione di memoria, dove trattiene la trama appena ricevuta, per il tempo necessario al controllo di errore. In presenza di un errore di ricezione della trama N+i, rilevato [141] [141]Sottolineiamo nuovamente l’importanza dei numeri di sequenza, che permettono al ricevitore di capire il numero della trama corrotta, grazie alla discontinuità dei numeri stessi. dopo la corretta ricezione di N+i+ 1, il ricevitore invia un nack(N+i), chiedendo con ciò al trasmettitore di andare indietro, ed inizia a scartare tutte le trame con numeri maggiori di N+i, finchè non riceve la N+i, e riprende le normali operazioni.
Se, trascorso un timeout, la N+i non è arrivata, si invia di nuovo un nack(N+i). Nel caso in cui invece si corrompa un ack, le operazioni continuano regolarmente, e l’ack successivo agisce da riscontro positivo anche per le trame per le quali non si sono ricevuti riscontri. Il trasmettitore deve quindi mantenere memorizzate tutte le trame trasmesse e non ancora riscontrate, fino ad un numero massimo, raggiunto il quale la trasmissione si arresta.
Una variante del metodo, idonea al caso in cui fenomeni di congestione di rete possano determinare la perdita dei nack, prevede l’uso di un timer al trasmettitore, per re-inviare le trame non riscontrate.

#### 5.5.2.2Selective repeat↓

L’origine di questo nome deriva dal fatto che non è più richiesto al trasmettitore di tornare indietro completamente, ma è sufficiente ritrasmettere solamente la trama che ha dato origine ad errore in ricezione, grazie alla capacità del ricevitore di memorizzare temporaneamente più trame, anche se ricevute fuori sequenza.
Come si nota in figura, a seguito della ritrasmissione della trama N+ 2 per cui si è ricevuto il nack, il trasmettitore continua a trasmettere nuove trame, fino al numero massimo previsto; in assenza di ulteriori ack, un timer determina la ritrasmissione delle trame non riscontrate.
Quando al ricevitore perviene la trama N+ 2, questo emette un ack(N+ 5), consentendo al trasmettitore di rilasciare tutta la memoria occupata dalle trame in sospeso, e di proseguire la trasmissione. La perdita di uno o più ack è gestita allo stesso modo che per go-back-N, così come per ogni nack inviato si inizializza un timer, allo scadere del quale ed in assenza di nuove trame ricevute, il nack è re-inviato.
Dal punto di vista del ricevitore, questo è più complicato che nel caso go-back-N, dato che adesso occorre riordinare le trame ricevute, che possono arrivare sequenziate con un ordine differente da quello naturale. Per questo motivo, anche il ricevitore deve predisporre delle memorie temporanee dove salvare le trame correttamente arrivate, successivamente a quella che invece conteneva errori, e di cui si attende la ritrasmissione.

#### 5.5.2.3Efficienza↓

Indichiamo con p la probabilità di dover chiedere la ritrasmissione di una trama [142] [142]Nel caso in cui l’integrità della trama sia protetta da un codice a blocchi (n,k) con dH=l+ 1, la probabilità che la trama contenga più di l errori e che quindi venga accettata dal ricevitore anche se errata, vale approssimativamente P(l+ 1,n)=⎛⎜⎝n l+ 1⎞⎟⎠pi (vedi formula (6.52↑)). Dato che il ricevitore accetta le trame che non hanno errori, oppure che hanno più di l errori, la probabilità che venga richiesta una ritrasmissione risulta p= 1 −P(0,n)−P(l+ 1,n). Considerando ora che un buon codice deve fornire P(l+ 1,n)≪P(0,n), si ottiene p≃1 −P(0,n)= 1 −(1  −Pe)n≃nPe, in cui Pe è la probabilità di errore sul bit (dato che (1 −Pe)n≃1  −nPe se nPe≪1). per la quale si sono rilevati errori di trasmissione, e con m il numero totale di trasmissioni necessarie alla sua corretta ricezione. Osserviamo quindi che m è una variabile aleatoria, descritta dalle probabilità
pM(1) = Pr(m= 1)= 1 −p pM(2) = p(1 −p) pM(3) = p2(1 −p) ⋮ pM(m) = pm− 1(1 −p)
in quanto la trama può essere ritrasmessa più volte, finché non si rilevano più errori. Pertanto, il numero medio di trasmissioni per una stessa trama è pari a
m = E{m}=∞⎲⎳m= 1mpM(m)=∞⎲⎳m= 1mpm− 1(1 −p)= = (1 −p)∞⎲⎳n= 0(n+ 1)⋅pn=(1 −p)(1)/((1  −p)2)=(1)/(1 −p)
in cui alla quarta eguaglianza si è posto n=m− 1, ed alla quinta si è tenuto conto della relazione espressa alla nota 8.4.2↓ di pag. 1↓, e del fatto che
∞⎲⎳k= 0kαk− 1=∞⎲⎳k= 1kαk− 1=∞⎲⎳k= 0(k+ 1)αk
Quindi, per trasmettere una frequenza binaria di fb bps (comprensivi di crc e overhead dei numeri di sequenza), occorre disporre di un canale di capacità fb⁄(1  −p) bps [143] [143]Dato che p aumenta con n (vedi pag. 1↑), l’efficienza del protocollo arq peggiora con l’aumentare della dimensione delle trame. Questo risultato determina l’esigenza di ricercare una soluzione di compromesso, dato che l’incidenza dell’overhead sulla dimensione complessiva della trama invece si riduce all’aumentare di n.. Questo risultato approssimato si applica ad un protocollo di tipo selective repeat, e trascurando gli errori sul canale a ritroso.

### 5.5.3Controllo di flusso↓

Si è illustrato che nei protocoli arq il trasmettitore, dopo un pò che non riceve nuovi ack, cessa a sua volta di inviare trame, dato che esaurisce la memoria temporanea in cui memorizzare le trame già inviate ed in attesa di riscontro. Nel caso in cui il ricevitore non sia in grado di smaltire in tempo i dati ricevuti, può scegliere di sospendere temporaneamente l’invio di riscontri, con il risultato di rallentare la velocità di invio dei dati. Questo meccanismo prende il nome di controllo di flusso, per l’evidente analogia idraulica, in cui una conduttura viene ristretta al fine di ridurre il flusso di liquido in transito.
Dato che il ritardo tra la sospensione dell’invio degli ack, e l’interruzione dell’invio di trame, dipende dalla dimensione delle memorie temporanee, e che questa dimensione incide allo stesso tempo anche sulla efficienza di utilizzo temporale del collegamento in condizioni di ricezione a piena velocità, svolgiamo alcune riflessioni sull’argomento.

#### 5.5.3.1Round trip time↓

E’ il tempo che intercorre tra l’inizio della trasmissione di una trama, e l’arrivo del relativo ack. La sua valutazione spesso si avvale della ipotesi di poter trascurare il tempo di trasmissione dell’ack, e quindi si ottiene RTT=tTx+ 2tp. Se la trasmissione avviene a velocità fb, allora in un tempo pari a RTT possono essere trasmessi Nba=fb⋅RTT bit, che possono essere pensati come il numero di bit in aria [144] [144]L’espressione “bit in aria” trae spunto dalla metafora di una coppia di giocolieri, posti ai due estremi di una piazza, che si lanciano una serie di clave. Il primo ne lancia in continuazione, e quando iniziano ad arrivare al secondo, questi le rilancia verso il primo. Nel momento in cui la clava partita per prima torna nelle mani del primo giocoliere, un certo numero di clave sono sospese a mezz’aria, e corrispondono approssimativamente al numero di bit trasmessi in un tempo di pari durata, con una frequenza pari al ritmo di lancio delle clave, e non ancora riscontrati.. Se la memoria temporanea del trasmettitore ha dimensioni W≥Nba, allora la trasmissione (senza errori) può avvenire senza soluzione di continuità, impegnando constantemente il collegamento.

#### 5.5.3.2Finestra scorrevole↓

La quantità massima di dati W che è possibile trasmettere senza ricevere un riscontro è indicata come finestra di trasmissione per il motivo che ora illustriamo. In figura

| f. di trasm. | f. di ric. | NMax
send and wait | 1 | 1 | 2
go back N | W | 1 | W+1
selective repeat | W | W | 2W+1

si mostra un gruppo di trame oggetto di una trasmissione; quelle già trasmesse ed in attesa di riscontro (da N+ 3 a N+ 6 in figura) sono racchiuse tra due confini, i bordi della finestra. Ogni volta che ne viene trasmessa una, il bordo superiore della finestra è spostato a destra, allargandola; ogni volta che si riceve un riscontro, è il bordo inferiore ad essere spostato a destra, restringendo così la finestra. In definitiva, il termine finestra trae origine dal fatto che, allo spostarsi dei bordi inferiore e superiore, la finestra si apre e si chiude.
La condizione di massima apertura della finestra identifica la quantità di memoria necessaria al trasmettitore per realizzare un protocollo arq, che quindi può essere ri-classificato in questi termini come indicato dalla tabella precedente, dove la colonna finestra di ricezione indica anche i requisiti di memoria al lato ricevente [145] [145]La ricezione di una sequenza di trame corrette, determina l’avanzamento alternato dei due bordi della finestra al ricevitore, che è inizialmente vuota, quindi contiene solo la trama ricevuta (avanza bordo superiore), e quindi è di nuovo svuotata, non appena viene trasmesso l’ack (ed avanza il bordo inferiore). In presenza di errori, il bordo inferiore non avanza, ma resta fermo sulla trama ricevuta con errori, e di cui si attende la ritrasmissione. Mentre il trasmettitore continua ad inviare trame, il ricevitore le memorizza e fa avanzare il bordo superiore, finché non siano state ricevute tutte quelle trasmissibili senza riscontro, e pari alla dimensione massima della finestra in trasmissione.. Notiamo infatti che mentre per send-and-wait è sufficiente la memoria di una sola trama, per go-back-N il trasmettitore deve ricordare fino ad un massimo di W trame in attesa di riscontro, e per selective repeat anche il ricevitore ha lo stesso vincolo, allo scopo di riodinare le trame ricevute fuori sequenza.

#### 5.5.3.3Numero di sequenza

Dato che non possono essere inviate più trame della dimensione della finestra, la loro numerazione può avvenire in forma ciclica, ossia utilizzando un contatore modulo NMax, come indicato alla tabella precedente. Ad esempio, per send-and-wait è sufficiente un contatore binario (0 − 1) perchè, nel caso in cui l’ack sia corrotto, il ricevitore possa riconoscere la trama ricevuta come duplicata anziché nuova; un ragionamento simile [146] [146]Se il trasmettitore invia tutte le W trame, ma tutti gli ack sono corrotti, allora la (W+ 1) -esima trama trasmessa è un duplicato della prima, ritrasmessa per time-out, ed il ricevitore può accorgersene solo se la trama reca un numero differente da quello della prima.
Per il caso selective repeat, vale un ragionamento simile, ma che per le differenze nella definizione del protocollo, porta ad un risultato diverso.
determina la necessità di usare W+ 1 numeri (0 −W) nel caso go-back-N, e 2W+ 1 numeri (0 − 2W) nel caso selective repeat.
L’uso di un numero di bit ridotto per indicare il numero di sequenza, permette di limitare la dimensione dell’overhead di trama; ad esempio, con una finestra di dimensione 7, l’uso di go-back-N richiede 8 diversi numeri di sequenza, che quindi possono essere codificati utilizzando 3 bit.
PrecSezione 5.4: Gestione degli errori di trasmissione SuCapitolo 5: Trasmissione dati in banda base Sezione: AppendiciSegue